%\course{ICE-EM/AMSI Summer School {\it Cryptography}}
%\heading{Summer}{RSA Cryptosystems}{2007}

The RSA cryptosystem is based on the difficulty of factoring large
integers into its composite primes.

Based on Fermat's little theorem, we know that $a^m \equiv 1 \bmod p$
exactly when $p-1$ divides $m$.  Therefore we recover the identity
$a^u \equiv a \bmod p$ where $u$ is of the form $1 + (p-1)r$.
Now given any $e$ such that $e$ and $p-1$ have no common divisors,
there exists a $d$ such that $ed \equiv 1 \bmod p-1$.  In other
words, $u = ed$ is of the form $1 + (p-1)r$.  This means that the
map
$$
a \mapsto a^e \bmod p
$$
followed by
$$
a^e \bmod p \mapsto (a^e \bmod p)^d
    \bmod p \equiv a^{ed} \bmod p = a \bmod p
$$
are inverse maps.  This only works for a prime $p$.

\begin{exercise}
\label{ex:pubkey_crypto:find_large_prime_compute_inverse_exponentiation}
Use Sage to find a large prime $p$ and to compute inverse exponentiation
pairs $e$ and $d$.  The following functions are of use:
\begin{center}
\verb!random_prime!, {\tt gcd}, {\tt xgcd}, and \verb!inverse_mod!.
\end{center}
The RSA cryptosystem is based on the fact that for primes $p$ and $q$ and
any integer $e$ with no common factors with $p-1$ and $q-1$, it is possible
to find an $d_1$ such that
$$
\begin{array}{l}
ed_1 \equiv 1 \bmod (p-1), \\
ed_2 \equiv 1 \bmod (q-1).
\end{array}
$$
Using the Chinese remainder theorem, it is possible to then find
the unique $d$ such that
$$
d = d_1 \bmod (p-1) \hbox{ and } d = d_2 \bmod (q-1)
$$
in the range $1 \le d < (p-1)(q-1)$. This $d$ has the property
that
$$
a^{ed} \equiv a \bmod n.
$$
The send a message securely, the public key $(e,n)$ is used.
First we encoding the message as an integer $a \bmod n$, then
form the ciphertext $a^e \bmod n$.  The recipient recovers the
message using the secret exponent $d$.
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:use_exponents_verify_identities}
Use your exponents $e$, $d$, verify the identities mod $p$:
$$
(a^e)^d \equiv a \bmod n,\
(a^d)^e \equiv a \bmod n, \hbox{ and }
a^{ed} \equiv a \bmod n,
$$
for various random values of $a$.

Note that after construction of $d$, the primes $p$ and $q$ are
not needed, but that without knowing the original factorization
of $n$, Fermat's little theorem does not apply, and finding the
inverse exponent for $e$ is considered a hard problem.
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:reproduce_private_key_with_factorization}
Use the above factorization to reproduce the private key $\tL$
(generated but not printed above) for this $\tK$.
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:arbitrary_choice_pubkey_prikey}
Why is the choice for which key is the public key and which
key is the private key arbitrary?  Practice encoding, decoding,
enciphering, and deciphering with the RSA cryptosystem. Why do
the member functions {\tt enciphering} and {\tt deciphering}
return the same values?
\end{exercise}

%\course{ICE-EM/AMSI Summer School {\it Cryptography}}
%\heading{Summer}{Diffie--Hellman and Discrete Logarithms}{2007}

An ElGamal cryptosystem is based on the difficulty of the
Diffie--Hellman problem:  Given a prime $p$, a primitive element
$a$ of $(\Z/p\Z)^* = \{ c \in Z/pZ : c \ne 0 \}$, and elements
$c_1 = a^x$ and $c_2 = a^y$, find the element $a^{xy}$ in
$(\Z/p\Z)^*$.

\begin{exercise}
\label{ex:pubkey_crypto:solve_discrete_log_then_solve_Diffie_Hellman_problem}
Recall the discrete logarithm problem: Given a prime $p$, a primitive
element $a$ of $(\Z/p\Z)^*$, and an element $c$ of $(\Z/p\Z)^*$,
find an integer $x$ such that $c = a^x$.
Explain how a general solution to the discrete logarithm problem
for $p$ and $a$ implies a solution to the Diffie--Hellman problem.
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:Fermat_little_theorem_primitive_element}
Fermat's little theorem tells us that $a^{p-1} = 1$ for all
$a$ in $(\Z/p\Z)^*$.  Recall that a primitive element $a$ has
the property that $\Z/(p-1)\Z \rightarrow (\Z/p\Z)^*$ given by
$x \mapsto a^x$ is a bijection.

\begin{enumerate}
\item
Show that $a$ is primitive if and only if $a^x = 1$ only when $p-1$
divides $x$.
\vspace{0.2cm}

\item
Let $p$ be prime $2^{32}+15$.  Show that $a = 3$ is a primitive
element of $(\Z/p\Z)^*$.  Use the Sage function {\tt log} to
compute discrete logarithms of elements of {\tt FiniteField(p)}
with respect to $a$.
\vspace{0.2cm}

\item
Let $p$ be the prime $2^{32}+61$.  Show that the element $a = 2$ is
a primitive element for $(\Z/p\Z)^*$.  Use the Sage function {\tt log}
to compute discrete logarithms of elements of {\tt FiniteField(p)}
with respect to $a$.
\end{enumerate}
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:compare_computation_time_discrete_log}
Compare the times to compute discrete logarithms in the
previous exercise.  Now factor $p-1$ for each $p$.  What difference
do you note?  Explain the timings in terms of the Chinese remainder
theorem for $\Z/(p-1)\Z$.
\end{exercise}

\begin{exercise}
\label{ex:pubkey_crypto:verify_factorization}
Let $p$ be the prime $2^{131}+1883$ and verify the factorization
$$
p-1 = 2\cdot 3\cdot 5\cdot 37\cdot 634466267339108669
                             \cdot 3865430919824322067.
$$
Let $a = 109$ and $c = 1014452131230551128319928312434869768346$
and set
$$
\begin{aligned}
n_5 & = (p-1) \hbox{ {\rm div} } 634466267339108669 \\
n_6 & = (p-1) \hbox{ {\rm div} } 3865430919824322067.
\end{aligned}
$$
Then verify that $c^{n_5} = a^{129n_5}$ and $c^{n_6} = a^{127n_6}$.
Find similar relations for
$$
\begin{array}{ll}
n_1 = (p-1) \hbox{ {\rm div} } 2 & n_3 = (p-1) \hbox{ {\rm div} } 5, \\
n_2 = (p-1) \hbox{ {\rm div} } 3 & n_4 = (p-1) \hbox{ {\rm div} } 37.
\end{array}
$$
and use this information to find the discrete logarithm of $c$ with
respect to~$a$.
\end{exercise}
